#include <iostream>
#include <cassert>
#include <ctime>
#include <cstdlib>
#include <iomanip>

using namespace std;

/*
2.设计包含 min 函数的栈。
定义栈的数据结构,要求添加一个 min 函数,能够得到栈的最小元素。
要求函数 min、push 以及 pop 的时间复杂度都是 O(1)。
*/

struct StackElem {
    int value;
    int min;
};

class Stack {
    private:
        enum {StackSize = 100};
        StackElem elems[StackSize];
        int pos;

    public:
        Stack();

        void push(int v);

        int& top();

        void pop();

        int min();

        bool isEmpty();
};

Stack::Stack() {
    pos = -1;
}

void Stack::push(int v) {
    elems[++pos].value = v;
    elems[pos].min = v;

    if (pos > 0 && v > elems[pos-1].min)
        elems[pos].min = elems[pos-1].min;
}

int& Stack::top() {
    assert(!isEmpty());
    return elems[pos].value;
}

void Stack::pop() {
    if (!isEmpty())
        pos--;
}

bool Stack::isEmpty() {
    return pos == -1;
}


int main() {
    Stack s;

    int size = 10;
    srand (time(NULL));

    while(size--) {
        s.push(random() % 1000);
    }
    while(!s.isEmpty()) {
        cout << s.top() << setw(4);
        s.pop();
    }
    cout << endl;


    return 0;
}
